package com.example.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 最近的公共祖先
 */
public class Tree4 {
    public static void main(String[] args) {

    }


    public static int lowestCommonAncestor(TreeNode root, int p, int q) {
        List<Integer> path1 = path(root.left, p);
        List<Integer> path2 = path(root.right, q);

        Collections.reverse(path1);

        for (Integer i : path1) {
            if (path2.contains(i)) {
                return i;
            }
        }

        return 0;
    }

    private static List<Integer> path(TreeNode root, int p) {
        List<Integer> path = new ArrayList<>();

        TreeNode target = root;
        while (target.val != p) {
            path.add(target.val);

            if (target.val < p) {
                target = target.right;
            } else {
                target = target.left;
            }
        }
        return path;
    }


}
